|
In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a sum of unit fractions, as e.g. 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first published systematic method for constructing such expansions is described in the Liber Abaci () of Leonardo of Pisa (Fibonacci). It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction. Fibonacci actually lists several different methods for constructing Egyptian fraction representations (, chapter II.7). He includes the greedy method as a last resort for situations when several simpler methods fail; see Egyptian fraction for a more detailed listing of these methods. As Salzer (1948) details, the greedy method, and extensions of it for the approximation of irrational numbers, have been rediscovered several times by modern mathematicians, earliest and most notably by ; see for instance and . A closely related expansion method that produces closer approximations at each step by allowing some unit fractions in the sum to be negative dates back to . The expansion produced by this method for a number ''x'' is called the greedy Egyptian expansion, Sylvester expansion, or Fibonacci–Sylvester expansion of ''x''. However, the term ''Fibonacci expansion'' usually refers, not to this method, but to representation of integers as sums of Fibonacci numbers. ==Algorithm and examples== Fibonacci's algorithm expands the fraction ''x''/''y'' to be represented, by repeatedly performing the replacement : (simplifying the second term in this replacement as necessary). For instance: : in this expansion, the denominator 3 of the first unit fraction is the result of rounding 15/7 up to the next larger integer, and the remaining fraction 2/15 is the result of simplifying (-15 mod 7)/(15×3) = 6/45. The denominator of the second unit fraction, 8, is the result of rounding 15/2 up to the next larger integer, and the remaining fraction 1/120 is what is left from 7/15 after subtracting both 1/3 and 1/8. As each expansion step reduces the numerator of the remaining fraction to be expanded, this method always terminates with a finite expansion; however, compared to ancient Egyptian expansions or to more modern methods, this method may produce expansions that are quite long, with large denominators. For instance, this method expands : while other methods lead to the much better expansion : suggests an even more badly-behaved example, 31/311. The greedy method leads to an expansion with ten terms, the last of which has over 500 digits in its denominator; however, 31/311 has a much shorter non-greedy representation, 1/12 + 1/63 + 1/2799 + 1/8708. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Greedy algorithm for Egyptian fractions」の詳細全文を読む スポンサード リンク
|